import math

def angle(v):
   res = math.atan2(v[1], v[0])
   if res < 0.0:
      res = 2 * math.pi + res
   return res

def angle_between(v1, v2):
   a1 = angle(v1)
   a2 = angle(v2)
   return a2 - a1

def border_intersect(pos, vec, width, height, xmin=-50, ymin=-50):
   height += 50
   width += 50
   if vec[0] == 0:
      if vec[1] >= 0:
         return (pos[0], height)
      else:
         return (pos[0], ymin)
   elif vec[1] == 0:
      if vec[0] >= 0:
         return (width, pos[1])
      else:
         return (ymin, pos[1])
   else:
      slope = vec[1] * 1.0 / vec[0]
      if vec[1] > 0:
         x_int = (height - pos[1]) / slope + pos[0]
      else:
         x_int = (ymin - pos[1]) / slope + pos[0]
      if vec[0] > 0:
         y_int = (width - pos[0]) * slope + pos[1]
      else:
         y_int = (xmin - pos[0]) * slope + pos[1]
      if x_int > xmin and x_int < width:
         y_int = (x_int - pos[0]) * slope + pos[1]
      else:
         x_int = (y_int - pos[1]) / slope + pos[0]
      return (int(x_int), int(y_int))
         
def closest(pos, sprites, method='euclid'):
   closest = sprites[0]
   min_distance = distance_methods[method](pos, closest.rect.center)
   for sprite in sprites[1:]:
      dist = distance_methods[method](pos, sprite.rect.center) 
      if dist < min_distance:
         min_distance = dist
         closest = sprite
   return closest
   
def distance(v1, v2):
   return math.sqrt(1.0 * ((v1[0] - v2[0]) ** 2 + (v1[1] - v2[1]) ** 2))

def dotp(v1, v2):
   return v1[0] * v2[0] + v1[1] * v2[1]

def interpolate(p1, p2, pos, isY=False):
   if isY:
      if pos > max(p1[1], p2[1]) or pos < min(p1[1], p2[1]):
         return None
   else:
      if pos > max(p1[0], p2[0]) or pos < min(p1[0], p2[0]):
         return None
   if p1[0] == p2[0]:
      if isY:
         return p1[0]
      else:
         return -1000
   elif p1[1] == p2[1]:
      if isY:
         return -1000
      else:
         return p1[1]
   else:
      slope = 1.0 * (p2[1] - p1[1]) / (p2[0] - p1[0])
      if isY:
         return int((pos - p1[1]) / slope + p1[0])
      else:
         return int(slope * (pos - p1[0]) + p1[1])

def intersect(x1, v1, x3, v3):
   x2 = v_add(x1, v1)
   x4 = v_add(x3, v3)
   
   try:
      return (((x1[0]*x2[1] - x1[1]*x2[0])*(x3[0] - x4[0]) - 
               (x3[0]*x4[1] - x3[1]*x4[0])*(x1[0] - x2[0])) /
              ((x1[0] - x2[0])*(x3[1]*x4[1]) - (x1[1] - x2[1])*(x3[0] - x4[0])),
              ((x1[0]*x2[1] - x1[1]*x2[0])*(x3[1] - x4[1]) - 
               (x3[0]*x4[1] - x3[1]*x4[0])*(x1[1] - x2[1])) /
              ((x1[0] - x2[0])*(x3[1]*x4[1]) - (x1[1] - x2[1])*(x3[0] - x4[0])))
   except ZeroDivisionError:
      return None

def lead_target(xs, vmax, xt, vt):
   a = float(vt[0] ** 2 + vt[1] ** 2 - vmax ** 2)
   b = 2.0 * ((xt[0] - xs[0])*vt[0] + (xt[1] - xs[0])*vt[1])
   c = float((xt[0] - xs[0])**2 + (xt[1] - xs[1])**2)
   desc = b**2 - 4*a*c
   if desc < 0:
      return None
   else:
      if a != 0.0:
         t1 = (-1*b + math.sqrt(desc)) / (2 * a)
         t2 = (-1*b - math.sqrt(desc)) / (2 * a)
         t = max(t1, t2)
      else:
         t = -1 * c / b
      dest = [xt[0] + t*vt[0], xt[1] + t*vt[1]]
      return dest
   
def length(v):
   return math.sqrt(1.0 * (v[0] ** 2 + v[1] ** 2))

def point_line_dist(st, end, pt):
   return abs((end[0] - st[0])*(st[1] - pt[1]) - (st[0] - pt[0])*(end[1] - st[1])) / math.sqrt((end[0] - st[0])**2 + (end[1] - st[1])**2)

def rect_line_collide(start, end, rect):
   intersections = list()
   leftint = interpolate(start, end, rect.left, False)
   if leftint >= rect.top and leftint <= rect.bottom:
      intersections.append((rect.left, leftint))
   rightint = interpolate(start, end, rect.right, False)
   if rightint >= rect.top and rightint <= rect.bottom:
      intersections.append((rect.right, rightint))
   topint = interpolate(start, end, rect.top, True)
   if topint >= rect.left and topint <= rect.right:
      intersections.append((topint, rect.top))
   bottomint = interpolate(start, end, rect.bottom, True)
   if bottomint >= rect.left and bottomint <= rect.right:
      intersections.append((bottomint, rect.bottom))
   if len(intersections) > 0:
      intersections.sort(key=lambda x: distance(start, x))
      return intersections[0]
   else:
      return None

def reflect(v, r):
   if r[0] < 0.0:
      r = s_mult(r, -1)
   angle = math.atan(r[1] * 1.0 / r[0])
   if angle > 0: #Positive slope
      mat = [[math.cos(2*angle), math.sin(2*angle)],
             [math.sin(2*(math.pi/2 - angle)), math.cos(2*(math.pi/2 - angle))]]
   else:
      mat = [[math.cos(2*angle), math.sin(2*angle)],
             [-1.0 * math.sin(2*(math.pi/2 + angle)), math.cos(2*(math.pi/2 + angle))]]
   return transform(mat, v)

def rotate(v, angle):
   return transform([[math.cos(angle), math.sin(angle)],
                     [-1.0 * math.sin(angle), math.cos(angle)]], v)

def s_div(v, s):
   return [int(v[0] * 1.0 / s), int(v[1] * 1.0 / s)]

def s_mult(v, s):
   return [v[0] * s, v[1] * s]

def set_length(v, l):
   cur_l = length(v)
   mult = l / cur_l
   return s_mult(v, mult)

def transform(mat, v):
   return [mat[0][0]*v[0] + mat[0][1]*v[1], mat[1][0]*v[0] + mat[1][1]*v[1]]

def towards(v1, v2, s, extend=False):
   dist = distance(v1, v2)
   connector = [v2[0] - v1[0], v2[1] - v1[1]]
   if dist >= s or extend:
      return set_length(connector, s)
   else:
      return connector

def v_add(v1, v2):
   return [v1[0] + v2[0], v1[1] + v2[1]]
   
def v_sub(v1, v2):
   return [v1[0] - v2[0], v1[1] - v2[1]]

def v_final(v1, v2, m1, m2, C):
   return [(m1*v1 + m2*v2 + m2*C*(v2-v1))*1.0/(m1+m2),
           (m1*v1 + m2*v2 + m1*C*(v1-v2))*1.0/(m1+m2)]

def x_distance(v1, v2):
   return abs(v1[0] - v2[0])

def y_distance(v1, v2):
   return abs(v1[1] - v2[1])

def main():
   for i in range(0, 900, 100) + [820] + [830] + [840]:
      print i
      print lead_target((0,0), 600, (300, 300), (-1 * i, 0))

distance_methods = {'x': x_distance,
                    'y': y_distance,
                    'euclid': distance}

if __name__ == '__main__':
   main()
